package study.datastructure.link.leetcode;

/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 */
class Client21 {
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        ListNode dHead = new ListNode(-1, null);
        ListNode p = dHead;
        ListNode p1 = list1;
        ListNode p2 = list2;

        while (p1 != null || p2 != null) {
            if (p1 == null) {
                p.next = p2;
                break;
            }
            if (p2 == null) {
                p.next = p1;
                break;
            }
            //添加到新链表 添加较小值
            if (p1.val < p2.val) {
                p.next = new ListNode(p1.val, null);
                p1 = p1.next;
                p = p.next;
            } else {
                p.next = new ListNode(p2.val, null);
                p2 = p2.next;
                p = p.next;
            }
        }   return dHead.next;

}

    /**
     * 构建新链表 比较关键的点是确定构建规则 有一个链表为空 停止循环
     * @param list1
     * @param list2
     * @return
     */
        public ListNode mergeTwoLists2 (ListNode list1, ListNode list2){
            ListNode dHead = new ListNode(-1, null);
            ListNode p = dHead;
            ListNode p1 = list1;
            ListNode p2 = list2;

            while (p1 != null && p2 != null) {
                //添加到新链表 添加较小值
                if (p1.val < p2.val) {
                    p.next = p1;
                    p1 = p1.next;
                } else {
                    p.next = p2;
                    p2 = p2.next;
                }
                p = p.next;
            }
            if (p1 == null) {
                p.next = p2;
            }
            if (p2 == null) {
                p.next = p1;
            }
            return dHead.next;
        }
    public ListNode mergeTwoListsByRecursion3 (ListNode list1, ListNode list2){
       ListNode head=new ListNode(-1,null);
       return recursion(list1,list2,head);
    }
    private ListNode recursion(ListNode list1,ListNode list2,ListNode head) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val) {
            head = list1;
            list1 = list1.next;
            head.next = recursion(list1, list2, head.next);
            return head;
        } else {
            head = list2;
            list2 = list2.next;
            head.next = recursion(list1, list2, head.next);
            return head;
        }
    }

    /**
     * 合并链表 比较重要的一点是确定返回的对象是 list1还是list2
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoListsByRecursion4 (ListNode list1, ListNode list2){
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val) {
            list1.next=mergeTwoListsByRecursion4(list1.next,list2);
            return list1;
        } else {
            list2.next=mergeTwoListsByRecursion4(list1,list2.next);
            return list2;
        }
    }
}